package com.lry.thompson;

import com.lry.input.Input;

import java.util.*;

public class NfaInterpreter {

    private Input input;
    private Nfa startNfa;

    public NfaInterpreter(Input input, Nfa startNfa) {
        this.input = input;
        this.startNfa = startNfa;
    }


    /**
     * 例如下nfa图：该图只能识别a|b
     *
     *   ↑----ε---> 节点1 ---a---> 节点2 ---ε---↓
     *节点5                                   节点6
     *   ↓_____ε___>节点3 ---b---> 节点4----ε--↑
     *
     *   假设用户输入为a的情况下，解释过程如下：
     *   计算头节点5的ε闭包，close(5) = {1,3,5}
     *   move({1,3,5},'a') = {2}
     *   计算节点2的ε闭包，close(2) = {2，6}
     *   到达终止状态6，算法结束，状态机可以识别a
     *
     *   如果用户输入的是aa呢？
     *   继续上述过程如下：
     *   move({2,6},'a') = {} 发现当输入为a时，节点2，6接受不了，识别失败
     */
    public void interpreter(){
        System.out.println("nfa Input string: ");

        input.renewInputBuffer();

        List<String> inputs = input.readInput();

        for (String str : inputs) {
            boolean lastAccepted = false;
            Set<Nfa> nfaSet = startNfaClosure();

            for(char c:str.toCharArray()){
                Set<Nfa> move = move(nfaSet, c);

                if(move.isEmpty()){
                    lastAccepted = false;
                    break;
                }

                nfaSet = εClosure(move);
                if(containsEndNfa(nfaSet)){
                    lastAccepted = true;
                }else{
                    lastAccepted = false;
                }
            }

            if (lastAccepted) {
                System.out.println("The Nfa Machine can recognize string: " + str);
            }else{
                System.out.println("The Nfa Machine can not recognize string: " + str);
            }
        }
    }

    /**
     * 判断集合中是否有终态节点
     * @param nfaSet
     * @return
     */
    private boolean containsEndNfa(Set<Nfa> nfaSet){
        if(null==nfaSet || nfaSet.isEmpty()){
            return false;
        }
        for(Nfa nfa:nfaSet){
            if(nfa.isEndNfa()){
                return true;
            }
        }
        return false;
    }

    private Set<Nfa> startNfaClosure(){
        Set<Nfa> nfaSet = new HashSet<>();
        nfaSet.add(startNfa);
        return εClosure(nfaSet);
    }

    /**
     * 计算ε闭包
     * @param nfaSet
     * @return
     */
    public Set<Nfa> εClosure(Set<Nfa> nfaSet){
        if(null==nfaSet || nfaSet.isEmpty()){
            return Collections.emptySet();
        }

        Stack<Nfa> stack = new Stack<>();
        for (Nfa nfa : nfaSet) {
            stack.push(nfa);
        }

        while(!stack.isEmpty()){
            Nfa nfa = stack.pop();
            if(nfa.edge==Nfa.EPSILON && nfa.next!=null){
                if(!nfaSet.contains(nfa.next)){
                    stack.push(nfa.next);
                    nfaSet.add(nfa.next);
                }
            }
            if(nfa.edge==Nfa.EPSILON && nfa.next2!=null){
                if(!nfaSet.contains(nfa.next2)){
                    stack.push(nfa.next2);
                    nfaSet.add(nfa.next2);
                }
            }
        }

        return nfaSet;
    }

    /**
     * move
     * @param nfaSet
     * @return
     */
    public Set<Nfa> move(Set<Nfa> nfaSet,char c){
        if(null==nfaSet || nfaSet.isEmpty()){
            return Collections.emptySet();
        }
        Set<Nfa> move = new HashSet<>();

        for (Nfa nfa : nfaSet) {
            if(null==nfa.next){
                continue;
            }
            if(nfa.edge ==c || (nfa.edge==Nfa.CCL && nfa.inputSet.contains((byte)c))){
                move.add(nfa.next);
            }
        }

        return move;
    }

}
